`:top
Das `!Schematheorem`! nach `F33f`_`[John H. Holland`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=John_H._Holland]`_`f behandelt das Konvergenzverhalten `F33f`_`[genetischer Algorithmen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Evolutionärer_Algorithmus]`_`f. Das Theorem beweist, dass sich `F33f`_`[Individuen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Individuum]`_`f mit überdurchschnittlicher `F33f`_`[Fitness`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Fitness_(Biologie)]`_`f mit höherer Wahrscheinlichkeit durchsetzen.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]
>>Contents
• `F0af`_`[Herleitung`#herleitung]`_`f
• `F0af`_`[Selektion`#selektion]`_`f
• `F0af`_`[Rekombination (Crossover)`#rekombination-crossover]`_`f
• `F0af`_`[Mutation`#mutation]`_`f
• `F0af`_`[Fazit`#fazit]`_`f
• `F0af`_`[Literatur`#literatur]`_`f
• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f
-─
>>Herleitung
Das Schematheorem betrachtet das `F33f`_`[Genom`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Genom]`_`f eines Individuums, in der Regel also eine `F33f`_`[Bitkette`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bitkette]`_`f, die Werte kodiert. Zunächst muss der Begriff `!Schema`! erläutert werden: Ein Schema ist ein `F33f`_`[Bitmuster`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bit]`_`f, das eine Menge von Bitketten repräsentiert. Ein Schema besteht aus den Zeichen `*0`* `*1`* oder `*#`*. Das Zeichen `*#`* fungiert als Platzhalter für eine `*0`* oder `*1`*.
Beispielsweise repräsentiert das Schema # # 101 # # {\\displaystyle \\#101\\#} die folgende Menge von Bitketten: { 01010 , 01011 , 11011 , 11010 } {\\displaystyle \\{01010,01011,11011,11010\\}} .
Das `*Schematheorem`* berechnet nun den `F33f`_`[Erwartungswert`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Erwartungswert]`_`f dafür, dass ein gewisses Schema H {\\displaystyle H} von einer Generation zur nächsten „überlebt“. Hierzu werden die drei zentralen Schritte eines Genetischen Algorithmus untersucht:
• `F33f`_`[Selektion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Selektion_(evolutionärer_Algorithmus)]`_`f
• `F33f`_`[Crossover`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Rekombination_(evolutionärer_Algorithmus)]`_`f (Rekombination)
• `F33f`_`[Mutation`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Mutation_(evolutionärer_Algorithmus)]`_`f
Es wird eine Population bestehend aus N {\\displaystyle N} binären Genomen der Länge l {\\displaystyle l} zu einem Zeitpunkt t {\\displaystyle t} betrachtet. Die verwendete `F33f`_`[Fitnessfunktion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Fitnessfunktion]`_`f f {\\displaystyle f} sei normiert und für alle Bitketten der Länge l {\\displaystyle l} definiert.
Im Zuge der Herleitung werden folgende Definitionen verwendet:
`!o ( H , t ) {\\displaystyle o(H,t)}`!
Anzahl der Genome zum Zeitpunkt t {\\displaystyle t} , die das Schema H {\\displaystyle H} enthalten.
`!d ( H ) {\\displaystyle d(H)}`!
`!Durchmesser`! des Schemas H {\\displaystyle H} , definiert als Länge der kürzesten Teilkette, die noch alle festen Bits des Schemas enthält, z. B d ( # # 0101 # # # # 1 # # # # ) = 7 {\\displaystyle d(\\#0101\\#\\#1\\#\\#)=7} .
`!b ( H ) {\\displaystyle b(H)}`!
Anzahl der festen Bits in H {\\displaystyle H} , z. B. b ( # # # # 0 # # # # 11 # # ) = 3 {\\displaystyle b(\\#\\#0\\#\\#11\\#)=3}
>>>Selektion
Da die Fitness normiert ist, gilt für die `F33f`_`[Wahrscheinlichkeit`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Wahrscheinlichkeit]`_`f p {\\displaystyle p} , dass eine bestimmte Elternkette H i {\\displaystyle H_{i}} aus einer Population ausgewählt wird: p ( H i ) = f ( H i ) {\\displaystyle p(H_{i})=f(H_{i})}
Seien nun ohne Einschränkung H 1 , … … , H o ( H , t ) {\\displaystyle H_{1},\\dotsc ,H_{o(H,t)}} alle diejenigen Bitketten der Population zur Zeit t {\\displaystyle t} , die das Schema H {\\displaystyle H} enthalten.
Die Fitness des Schemas H {\\displaystyle H} wird dann definiert als Durchschnitt der Fitness aller Individuen: f ( H ) = f ( H 1 ) + … … + f ( H o ( H , t ) ) o ( H , t ) {\\displaystyle f(H)={\\frac {f(H_{1})+\\dotsc +f(H_{o(H,t)})}{o(H,t)}}} .
Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die H {\\displaystyle H} enthält, ist somit: P S e l = p ( H 1 ) + … … + p ( H o ( H , t ) ) = o ( H , t ) f ( H ) . {\\displaystyle P_{Sel}=p(H_{1})+\\dotsc +p(H_{o(H,t)})=o(H,t)f(H).}
Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide H {\\displaystyle H} enthalten, ausgewählt werden, gilt: P 2 = P S e l 2 {\\displaystyle P_{2}={P_{Sel}}^{2}} .
>>>Rekombination (Crossover)
Beim 1-Point-Rekombination wird zunächst ein Trennpunkt zwischen den Bitstellen 1 und `*l-1`* gewählt. Falls beide Elternteile H {\\displaystyle H} enthalten, so enthält auch die Tochterkette dieses Schema. Enthält nur eine Elternkette das Schema, so wird H {\\displaystyle H} im Mittel in der Hälfte der Fälle weitergegeben, falls es nicht beim Crossover selbst durchtrennt wird.
Die Wahrscheinlichkeit, dass es nicht durchtrennt wird, ist: P C u t ¯ ¯ = 1 − − d ( H ) − − 1 l − − 1 . {\\displaystyle {\\overline {P_{Cut}}}=1-{\\frac {d(H)-1}{l-1}}.}
Damit gilt für die Wahrscheinlichkeit W {\\displaystyle W} , dass beim Crossover das Schema H {\\displaystyle H} weitergegeben wird: W ≥ ≥ P 2 + 1 2 P 1 P C u t ¯ ¯ . {\\displaystyle W\\geq P_{2}+{\\frac {1}{2}}P_{1}{\\overline {P_{Cut}}}.}
Falls beim Crossover das Schema H {\\displaystyle H} durchtrennt wird, besteht die Möglichkeit, dass das fehlende Teilstück an passender Stelle in der anderen Elternkette enthalten ist. Daher rührt die Ungleichung. Falls 2-Point-Crossover durchgeführt wird, hat das lediglich Auswirkungen auf P C u t {\\displaystyle P_{Cut}} , die Wahrscheinlichkeit, dass das Schema durchtrennt wird, steigt.
>>>Mutation
Sei p {\\displaystyle p} die Mutationswahrscheinlichkeit, das heißt, jedes Bit der neuen Kette wird mit der Wahrscheinlichkeit p {\\displaystyle p} negiert. Dies bedeutet, dass das Schema H {\\displaystyle H} mit b ( H ) {\\displaystyle b(H)} festen Bits mit der Wahrscheinlichkeit P M u t ¯ ¯ = ( 1 − − p ) b ( H ) {\\displaystyle {\\overline {P_{Mut}}}=(1-p)^{b(H)}} erhalten bleibt.
Wird dieser Effekt berücksichtigt, so ergibt sich für die Wahrscheinlichkeit W ′ {\\displaystyle W'} , dass eine durch die Operatoren Crossover und Mutation erzeugte Kette das Schema H {\\displaystyle H} enthält:
W ′ = W P M u t ¯ ¯ {\\displaystyle W'=W{\\overline {P_{Mut}}}}
W ′ ≥ ≥ ( P 2 + 1 2 P 1 P C u t ¯ ¯ ) P M u t ¯ ¯ {\\displaystyle W'\\geq \\left(P_{2}+{\\frac {1}{2}}P_{1}{\\overline {P_{Cut}}}\\right){\\overline {P_{Mut}}}}
W ′ ≥ ≥ ( P S e l 2 + P S e l ( 1 − − P S e l ) ( 1 − − d ( H ) − − 1 l − − 1 ) ) ( 1 − − p ) b ( H ) . {\\displaystyle W'\\geq \\left(P_{Sel}^{2}+P_{Sel}\\left(1-P_{Sel}\\right)\\left(1-{\\frac {d(H)-1}{l-1}}\\right)\\right)(1-p)^{b(H)}\\,.}
Mit P S e l = o ( H , t ) f ( H ) {\\displaystyle P_{Sel}=o(H,t)f(H)} .
>>>Fazit
Werden also insgesamt N {\\displaystyle N} neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema H {\\displaystyle H} zum Zeitpunkt t + 1 {\\displaystyle t+1} enthalten: ⟨ ⟨ o ( H , t + 1 ) ⟩ ⟩ = N W ′ {\\displaystyle \\langle o(H,t+1)\\rangle =NW'}
Die letzten beiden Formeln zeigen, dass Schemata mit überdurchschnittlicher Fitness und kleinem Durchmesser sich mit großer Wahrscheinlichkeit durchsetzen. Die Reproduktionswahrscheinlichkeit steigt aber auch mit der Häufigkeit eines Schemas o ( H , t ) {\\displaystyle o(H,t)} . Das heißt, ein durchschnittliches Schema kann sich innerhalb einer Population durchsetzen, wenn es oft genug vorkommt. Dieser Effekt wird `!genetisches Driften`! genannt.
Weiterhin verdient der Faktor P M u t ¯ ¯ = ( 1 − − p ) b ( H ) {\\displaystyle {\\overline {P_{Mut}}}=(1-p)^{b(H)}} Beachtung. Eine hohe Mutationsrate p {\\displaystyle p} bewirkt eine verstärkte Destruktion erfolgreicher Muster. Andererseits ist eine gewisse Mutationshäufigkeit nötig, um den Suchraum möglichst umfassend zu durchsuchen. Durch Justierung von p {\\displaystyle p} kann also die Suchaktivität des Algorithmus gesteuert werden.
>>Literatur
• David White: An Overview of Schema Theory. In: Graduate Journal of Mathematics. Band 3, Nr. 2, 2018, S. 37–59, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.48550/arXiv.1401.2651.
>>Einzelnachweise
`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f John H. Holland: Adaptation in natural and artificial systems : an introductory analysis with applications to biology, control, and artificial intelligence. 1st MIT Press ed Auflage. MIT Press, Cambridge, Mass. 1992, ISBN 0-585-03844-9.
`c`F0af`_`[↑ Back to top`#top]`_`f`a